/**
 * 插入排序, 需要额外的地址空间
 * 稳定的排序方法
 */

 let arr = [4, 89, 90, 28, 8, 8, 10, 11]

 function insertSort(arr) {
    let length = arr.length, j, temp

    for(let i =0; i< length; i++) {
       j =i
       temp = arr[i]

       while(j > 0 && arr[j -1] > temp){
           arr[j] = arr[j -1]
           j-- 
       }
       arr[j] = temp
    }
 }
